Though the field of signal communication through host media signals, such as image and audio signals, is well developed, challenges persist in providing reliable communication, with sufficient data capacity, while not impairing perceptual quality of the host signal. Within this field, an approach for signal communication in host signals is often referred to as “digital watermarking.” Digital watermarking most often refers to a form of signaling in which a data channel is embedded within a host or cover signal while minimizing the impact of the embedding on perceptual quality of the host, e.g., when that host signal is perceived by humans. Relatedly, steganographic encoding refers to methods of communicating data in a cover signal (including ambient background signals) so that the data is hidden from ordinary human observation. Steganographic decoding is the complementary process of recovering the hidden data from a received signal.
The boundaries of digital watermarking blur as this type of signaling overlaps with other signaling techniques with similar attributes or application objectives. Various techniques and applications exist for signaling in host signals like still images, video, and audio. For many applications, the data channel is embedded and extracted digitally, yet must survive conversion to and from the analog domain as well as distortion. Popular examples include encoding digital data in images applied to physical objects, or transmitting digital data in sound signals transmitted from speakers to mobile devices in noisy venues. The data signal encounters distortion at every step along its path, from the conversion into rendered form, the mixing with other signals and background noise, and the capture of the signal within a sensor of the receiver. In some communication channels, there may be negligible host signal content, such as when signaling within regions devoid of image content on a package or document, or signaling through an audio like data channel at frequency ranges at or near the limits of human hearing (e.g., around 20 Hz). In other cases, data carrying symbols like one dimensional (1D) or two dimensional (2D) bar codes, which are not intended to be embedded within host content, are nonetheless modified to convey graphical designs as well as machine readable data elements. Additionally, conventional 2D code matrices are made less visually obtrusive by printing them with less visible inks or varnish layers and detecting the codes with illumination, sensors and signal processing tailored to amplify the data signal. As another example, 2D codes may be adapted to be less visible by printing at higher resolution and repeated on an object. Colors and higher dimensional multi-spectral bands, just within or just beyond the limits of the human visual system, may also be leveraged as additional hosts for auxiliary data channels increase capacity, reliability and/or perceptual quality. Use of redundancy encoding and error correction techniques enable such bar code adaptations or glyph codes to be combined with other image content on packaging, documents, labels, and other types of objects, in a manner that is less perceptible or not interfering with the legibility of other visual content with which it is mixed. These types of approaches tend to blur the boundaries of what might be considered to be digital watermarking, extending our robust signaling methodologies to application domains with little or sparse host content within which to embed the data channel.
Nevertheless, this document is concerned with robust auxiliary data signal communication without being confined to a particular definition of digital watermarking or data signaling technique. For many applications of robust signaling, the challenge is balancing the competing objectives of maintaining reliability in the face of distortion, expanding data carrying capacity, and achieving sufficient perceptual quality. This is always a challenge because the objectives conflict. For example, increasing the data capacity impacts reliability. Increasing signal strength to improve reliability can introduce modifications to the host signal that degrade its perceptual quality and/or limit information carrying capacity.
An additional challenge of embedding a data channel in a host medium is that the host becomes a source of noise or interference with data channel. Some approaches seek to mitigate interference by employing information theoretic approaches to encode an auxiliary data channel within the host channel. For example, data coding patterns may be selected that minimize changes to the host signal. These techniques are sometimes categorized as “informed embedding,” as the encoder operation is informed by specific information characteristics of the host to embed data with reduced host distortion, increased capacity, and/or increased reliability. These techniques may be employed in combination with additional methods for mitigating host signal interference.
In our prior work, we have developed schemes for mitigating host signal interference through differential encoding that is paired with complementary signal detection or decoding operations. See, for example, US Patent Publications 20140142958 (with differential encoding applied in audio channels) and 20100150434 (with differential encoding applied to signals encoded in color channels of image content), which are incorporated by reference. Differential encoding generally refers to a scheme in which data signal elements are encoded in differential relationships at locations within a host channel. These data signal elements are mapped to corresponding embedding locations within the host channel.
There are a myriad of ways to prepare the signal elements for encoding, and as such, differential encoding applies to many different data signaling strategies. To illustrate, a non-exhaustive list includes selecting code symbols, applying error correction, selecting signal features of the host to carry a signal element. U.S. Pat. No. 6,122,403 provides examples of auxiliary data signals modulated on carriers with positive and negative signal elements. 20140142958 and 20100150434 illustrate different examples of how to exploit differential encoding.
Host signal interference can be mitigated when the signal detector and data extraction processes exploit the differential arrangement to suppress the host signal. To facilitate this operation in the decoding process, differential encoding is applied to embedding locations of a host signal where the values of the host signal are correlated. The host is suppressed by decode operations on the received signal that combine the differentially encoded information constructively, while cancelling correlated host signal components, increasing the signal to noise ratio of the data signal to the host. Examples of these types of operations are provided in 20140142958 and 20100150434.
These techniques for improving the signal reliability become more difficult to implement in applications where the embedded data signal is likely to be distorted in ways that make synchronization difficult. Such distortion can crop or truncate portions of the embedded signal, or warp its structure (e.g., a geometric or temporal distortion, including projective transformations). The application requirement, for example, may dictate that the data signal be reliably recovered from small portions of host signals at arbitrary locations and geometric transformations (including perspective transforms). Image capture of an object or document with 2D sensor in a camera or scanner introduces geometric distortion and cropping of the signal, in addition to distortion introduced in printing, deformation and degradation of the object. Audio capture of ambient audio crops and samples the signal with temporal distortion, in addition to distortion introduced in generating the audio, compressing it, and mixing it with ambient noise and echoes. Some applications further require that portions of the host convey different data, such that a stream of the host signal provides a reliable channel for a stream of data.
This distortion dictates that the data channel be designed to be robust to it. One way to do this is to use encoding strategies that employ attributes of the host that are robust to geometric or temporal distortion, or employ a host modulation scheme that is robust to distortion. In addition, the design of the encoded signal often needs to provide signal structure that facilitates detection and synchronization. This signal structure, to the extent it occupies a portion of the channel where data could otherwise be encoded, limits data capacity. Another implication of introducing synchronization components within the signaling scheme is that these components can degrade perceptual quality, for example, by introducing un-wanted human perceptible elements. In some schemes, a synchronization signal may also interfere with the data carrying signal in the channel. There is a need for data signaling that is both robust to de-synchronization, without substantially interfering with data signal capacity.
The application of the signaling scheme tends to have unique design constraints that emphasize some combination of the above mentioned considerations in addition to others. To illustrate, we provide a few examples, without intending to limit our scope to them. One application domain is conveying a data signal in a physical object and reading it from a signal sensed from sensors on a mobile device or other consumer electronic equipment. In the realm of conveying signals in physical objects, robustness requirements include the ability of the data to survive distortions due to digital processing, like compression, degradation encountered in applying the signal to the object (e.g., 2D and 3D printing, engraving, etching on a 2D or even 3D curved or irregular surface) and in sensing the signal from the object.
Another application domain is conveying the signal in a video display or audio speaker output and reading it from a signal sensed from sensors on a mobile device or other consumer electronics. Image and audio like signaling present challenges unique to these signal types. Printing technologies pose limitations due to the types of inks and colors employed, registration among printing plates, and other limits on the control of application of ink to a substrate, including the limits on print quality and resolution of print primitives to retain the data channel (line art, half-toning, screen angle, dot gain, etc.). Display technologies pose limitations in terms of screen resolution, color format, screen format (including aspect ratio, key-stoning, etc.), refresh rate, etc. The target host signal content poses limitations as well. For image based signaling, the nature of the imagery or artwork, or absence thereof, limits the available data encoding channel. Document content differs from package or label content. Video formats and codecs, and video content quality and data rate vary as well. Audio signaling, particular in noisy environments, present other challenges, with different forms of noise, distortion and interference.
The design of a signaling scheme must also account for practical challenges posed by constraints on digital circuitry, processors and memory for encoding and decoding. These include computational efficiency, power consumption, memory consumption, memory bandwidth, use of network bandwidth, cost of hardware circuitry or programmable processors/circuitry, cost of designing and integrating encoders and decoders within signal transmitter and receiver, equipment, etc. For example, some encoding schemes may provide optimized encoding or decoding, but may not be applicable because they are too slow for encoding or decoding in real time, e.g., as the host signal is being transmitted, received, updated, or being processed with multiple other signal processing operations concurrently.
In this document, we detail various modulation schemes, including schemes for generating signals, and encoding and decoding them in data channels. We describe differential modulation schemes that encode a data channel within host signal or noisy environments in a manner that is robust, flexible to achieve perceptual quality constraints, and provides improved data capacity. Differential arrangements applied by the encoder enable a decoder to suppress host signal or other background signal interference when detecting, synchronizing and extracting an encoded data channel. They also enable the incorporation of implicit or explicit synchronization components, which are either formed from the data signal or are complementary to it.
One aspect of the invention is a method of encoding auxiliary data in a host image signal. This method generates an auxiliary data signal comprised of variable data elements. It maps each of the variable data elements to plural blocks within the host image signal. Each block comprises neighboring embedding locations within the host image signal. For each variable data element, the method modulates the host image signal according to the variable data element to embed the variable data element in corresponding plural blocks. Within each of the corresponding plural blocks, the modulation process modulates the host image by establishing differential relationships between the variable data element in non-adjacent embedding locations within each block.
Various alternative forms of this technology are described, including apparatus, digital logic modules, and programmed processor modules.